import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2024/5/27 22:28
 * @description: 力扣51
 * .    https://leetcode.cn/problems/n-queens/ N皇后
 *      华为谷歌亚马逊
 * @Author LittleNight
 */
public class likou51 {

    List<List<String>> ret;
    char[][] path;
    int n;
    boolean[] checkCol, checkDigit1, checkDigit2;
    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        ret = new ArrayList<>();
        path = new char[n][n];
        checkCol = new boolean[n];
        checkDigit1 = new boolean[n * 2];
        checkDigit2 = new boolean[n * 2];
        // 先初始化 path 数组,
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                path[i][j] = '.';
            }
        }

        dfs(0); // 只需要传入一个行即可
        return ret;
    }

    private void dfs(int row) {
        // 越界也就是递归出口了
        if(row == n) {
            // 把 path 中的字符转成字符串, 添加到ret中
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                char[] chars = path[i];
                tmp.add(new String(chars));
            }
            ret.add(new ArrayList<>(tmp));
            return;
        }
        // 遍历这一行中的每一个列, 判断是否能放
        for (int col = 0; col < n; col++) {
//            if(checkCol[col] == false && checkDigit1[col] == false && checkDigit2[col] == false) {
            if(checkCol[col] == false && checkDigit1[col - row + n] == false && checkDigit2[col + row] == false) {
                // 这个位置可以放
                path[row][col] = 'Q';
                checkCol[col] = checkDigit1[row - col + n] = checkDigit2[col + row] = true; // 表示这一行有元素了
                dfs(row + 1); // 去下一层看看
                // 回溯-恢复现场
                path[row][col] = '.';
                checkCol[col] = checkDigit1[row - col + n] = checkDigit2[col + row] = false; // 表示这一行没有元素了
            }
        }
    }
}
